package main.leetcode.offer.firstround.from03to50;

/**
 * 11.旋转数组的最小数字
 *
 * <p>把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5]
 * 的一个旋转，该数组的最小值为1。
 *
 * <p>示例 1： 输入：[3,4,5,1,2] 输出：1
 *
 * <p>示例 2： 输入：[2,2,2,0,1] 输出：0
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex11 {
    public static void main(String[] args) {
        int[] nums = {3, 3, 1, 3};
        System.out.println(new ex11().minArray(nums));
    }
    // 二分法（减治）
    public int minArray(int[] numbers) {
        if (numbers.length == 1) return numbers[0];
        int l = 0, r = numbers.length - 1, mid;
        while (l < r) {
            if (numbers[l] < numbers[r]) return numbers[l];
            mid = (l + r) >>> 1; // 无符号右移
            if (numbers[mid] > numbers[r]) l = mid + 1;
            else if (numbers[mid] < numbers[r]) r = mid;
            else {
                r--; // {3, 3, 1, 3}
            }
        }
        return numbers[l];
    }
}
